package leetcode

import (
	"sort"
	"strconv"
)

func isDigit(b byte) bool { return '0' <= b && b <= '9' }
func isLower(b byte) bool { return 'a' <= b && b <= 'z' }

func countOfAtoms(formula string) string {
    stack := []map[string]int{{}}
    index := 0
    length := len(formula)

    // 扫描数字
    parseNum := func() (res int) {
        if index == length || !isDigit(formula[index]) {
            return 1
        }

        for ; index < length && isDigit(formula[index]); index ++ {
            res = res * 10 + int(formula[index] - '0')
        }

        return 
    }

    // 遍历
    for index < length {
        switch formula[index] {
        case '(':
            index ++
            stack = append(stack, map[string]int{})

        case ')':
            mp := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            index ++
            v := parseNum()
            for atom, num := range mp {
                stack[len(stack) - 1][atom] += num * v
            }

        default:
            mark := index
            for index ++; index < length && isLower(formula[index]); index ++ {}
            atom := formula[mark : index]
            stack[len(stack) - 1][atom] += parseNum()
        }
        
    }

    // 整理数据，形成返回值
    mp := stack[0]
    tmpStr := make([]string, len(mp))

    // 字典序排列原子
    for atom := range mp {
        tmpStr = append(tmpStr, atom)    
    }

    sort.Strings(tmpStr)
    
    // 加上数字
    var ans string

    for _, atom := range tmpStr {
        ans += atom
        if num := mp[atom]; num > 1 {
            ans += strconv.Itoa(num)
        }
    } 

    return ans









}
